package arithmetic1.stringMatch;

/*
    kmp算法
 */
public class KmpMatch {
    public static void main(String[] args) {
        String str1="gfkldl kjldfd";
        String str2="df";
        int index=kmpMatch(str1,str2,next(str2));
        System.out.println(index);
    }

    //kmp算法
    public static int kmpMatch(String str1,String str2,int[] next){
        for(int i=0,j=0;i<str1.length();i++){
            while(j>0 && str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if(str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if(j==str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }

    //生成模式串的next数组
    public static int[] next(String str){
        int next[]=new int[str.length()];
        next[0]=0;  //当字符串长度为1的时候str的前缀与后缀公共序列的最大长度为0
        for(int i=1,j=0;i<str.length();i++){
            while(j>0 && str.charAt(i)!=str.charAt(j) ){
                j=next[j-1];
            }
            if(str.charAt(i)==str.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}
